using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography.X509Certificates;
using System.Threading.Tasks;

namespace DataStructure
{
    public class BST1<T> where T: IComparable<T>
    {
        private class Node
        {
            public T data;
            public Node left, right;
            
            public Node(T data)
            {
                this.data = data;
                left  = null;
                right = null;
            }
        }
        
        private Node root;
        private int count;
        
        public BST1()
        {
            root = null;
            count = 0;
        }
        public int Count => count;
        public bool IsEmpty => count == 0;
        
        //向二叉树中非递归添加元素
        public void add(T t)
        {
            //如果根节点为空，则直接创建根节点
            if (root == null)
            {
                root = new Node(t); //创建根节点
                count++;
                return;
            }
            
            Node pre = null; //记录当前节点的前一个节点
            Node cur = root;  //从根节点开始遍历
            
            while (cur != null)
            {
                //数中不允许添加重复元素
                if (t.CompareTo(cur.data) == 0)
                    return;
                    
                //先记录cur的位置,再移动cur
                pre = cur;
                
                if (t.CompareTo(cur.data) < 0)
                    cur = cur.left; //向左移动 在左子树中查找
                else//t.CompareTo(cur.data) > 0 
                    cur = cur.right;//向右移动 在右子树中查找
            }
            
            //while循环结束cur==null,通过元素t创建新结点放到cur中
            cur = new Node(t);
            
            //判断cur是pre的左孩子还是右孩子
            if (t.CompareTo(cur.data) < 0)
                pre.left = cur;     //cur是pre的左孩子
            else  //e.CompareTo(pre.e) > 0
                pre.right = cur;    //cur是pre的右孩子

            count++;
        }
    
        //向二叉树中递归添加元素
        public void Add(T t)
        {
            root = Add(root, t);
        }
        //以node为根的树中添加元素e，添加后返回根节点node
        private Node Add(Node node, T t)
        {
            if (node == null)
            {
                count++;
                return new Node(t);
            }     
            
            if (t.CompareTo(node.data) < 0)
                node.left = Add(node.left, t);
            else if (t.CompareTo(node.data) > 0)
                node.right = Add(node.right, t);

            return node;
        }
        public bool Contains(T t)
        {
            return Contains(root, t);
        }
        private bool Contains(Node node, T t)
        {
            if (node == null)
                return false;

            if (t.CompareTo(node.data) == 0)
                return true;
            else if (t.CompareTo(node.data) < 0)
                return Contains(node.left, t);
            else//t.CompareTo(node.data) > 0
                return Contains(node.right, t);
        }
        
        
        //中序遍历
        public void InOrder()
        {
            InOrder(root);
        }
        private void InOrder(Node node)
        {
            if (node == null)
                return;

            InOrder(node.left);
            Console.WriteLine(node.data);
            InOrder(node.right);
        }
        
        //后序遍历
        public void PostOrder()
        {
            PostOrder(root);
        }
        private void PostOrder(Node node)
        {
            if (node == null)
                return;

            PostOrder(node.left);
            PostOrder(node.right);
            Console.WriteLine(node.data);
        }
        
        //层序遍历
        public void LevelOrder()
        {
            Queue<Node> queue = new Queue<Node>();
            queue.Enqueue(root);
            
            while (queue.Count != 0)
            {
                //出对
                Node cur = queue.Dequeue();
                Console.WriteLine(cur.data);
                
                //入队
                if (cur.left != null)
                    queue.Enqueue(cur.left);
                if (cur.right != null)
                    queue.Enqueue(cur.right);
            }
        }
        
        //寻找二叉树的最小元素
        public T Min()
        {
            if(IsEmpty)
                throw new ArgumentException("空树！");
                
            return Min(root).data;
        }
        private Node Min(Node node)
        {
            if (node.left == null)
                return node;

            return Min(node.left);
        }
        
        // 寻找二叉查找树的最大元素
        public T Max()
        {
            if (IsEmpty)
                throw new ArgumentException("空树！");

            return Max(root).data;
        }
        private Node Max(Node node)
        {
            if (node.right == null)
                return node;

           return Max(node.right);
        }
        
        //从二叉查找树中删除最小值的结点
        public T RemoveMin()
        {
            T del = Min();
            root = RemoveMin(root);
            return del;
        }

        private Node RemoveMin(Node node)
        {
            if (node.left == null)
            {
                count--;
                return node.right;
            }
            
            node.left = RemoveMin(node.left);
            return node;
        }
        
        //删除最大值的结点
        public T RemoveMax()
        {
            T del = Max();
            root = RemoveMax(root);
            return del;
        }

        private Node RemoveMax(Node node)
        {
            if (node.right == null)
            {
                count--;
                return node.left;
            }
            
            node.right = RemoveMax(node.right);
            return node;
        }
        
        //删除元素t的结点
        public void Remove(T t)
        {
            root = Remove(root, t);
        }

        private Node Remove(Node node, T t)
        {
            if (node == null)
                return null;

            if (t.CompareTo(node.data) < 0)
            {
                node.left = Remove(node.left, t);
                return node;
            }
            else if (t.CompareTo(node.data) > 0)
            {
                node.right = Remove(node.right, t);
                return node;
            }
            else//e.CompareTo(node.e) == 0
            {
                //删除的结点只有左孩子
                if (node.right == null)
                {
                    count--;
                    return node.left;
                }
                //只有右孩子
                if (node.left == null)
                {
                    count--;
                    return node.right;
                }
                //左右孩子都有
                //找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
                //用这个节点顶替待删除节点的位置
                Node s = Min(node.right);
                s.right = RemoveMin(node.right);
                s.left = node.left;
                
                return s;
            }
        }
        //二叉树的最大高度
        public int MaxHeight()
        {
            return MaxHeight(root);
        }

        private int MaxHeight(Node node)
        {
            if (node == null)
                return 0;

            // int left = MaxHeight(node.left);
            // int right = MaxHeight(node.right);
            // return Math.Max(left, right) + 1;
            
            return Math.Max(MaxHeight(node.left), MaxHeight(node.right)) + 1;
        }
    }
}